package leetcode.easy.q69;

import lombok.extern.slf4j.Slf4j;

public class Q {
    public static void main(String[] args) {
        System.out.printf(new Solution().mySqrt(Integer.MAX_VALUE) + "");
        System.out.printf(new Solution().mySqrt(9) + "");
        System.out.printf(new Solution().mySqrt(15) + "");
        System.out.printf(new Solution().mySqrt(16) + "");
    }
}

@Slf4j
class Solution {
    /**
     * n<=x/n && (n+1)>x/(n+1) return n;
     */
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int min = 0;
        int max = x;
        int mid = 0;
        while ((mid = min + (max - min) / 2) > min) {
            log.info("min:{},mid:{},max:{},x:{}",min,mid,max,x);
            if (mid > x / mid) {
                max = mid;
            } else if (mid == x / mid) {
                return mid;
            } else {
                min = mid;
            }
        }
        return min;
    }
}